package com.yt.ds.chapter4;

/**
 * @Author: lzf
 * @Date: 2020/7/28 17:04
 * @Description: 连通分量
 */
public class CC {
    private boolean[] marked;
    private int[] id;
    private int count = 0;

    CC(Graph graph) {
        marked = new boolean[graph.getVertexNum()];
        id = new int[graph.getVertexNum()];
        for (int i = 0; i < graph.getVertexNum(); i++) {
            if (!marked[i]) {
                dfs(graph, i);
                count++;
            }
        }
    }

    /**
     * 利用深度优先计算连通量
     */
    private void dfs(Graph graph, int v) {
        marked[v] = true;
        id[v] = count;
        for (int w : graph.adj(v)) {
            if (!marked[w]) {
                dfs(graph, w);
            }
        }
    }

    /**
     * 描述：判断点v和点w是否连通
     *
     * @param v 点v
     * @param w 点w
     * @return "boolean"
     * @date: 2020/7/28 17:07
     */
    public boolean connected(int v, int w) {
        return id[v] == id[w];
    }

    /**
     * 描述：判断有几个连通量
     *
     * @return "int"
     * @date: 2020/7/28 17:08
     */
    public int count() {
        return count;
    }

    /**
     * 描述：判断点v所在的连通量为第几个
     *
     * @param v 点v
     * @return "int"
     * @date: 2020/7/28 17:08
     */
    public int id(int v) {
        return id[v];
    }
}
